package com.baishancloud.log.common.util

import scala.util.control.Breaks._

/**
 * 数组操作
 *
 * @author ziqiang.wang 
 * @date 2021/12/24 11:27
 */
object ArrayUtil {

  /**
   * 二分查找<br>
   * 根据给定数组、指定值以及compare条件，返回可能的数组下标。
   *
   * @param a       数组，要求元素已经自然排序
   * @param value   待查找值
   * @param compare 比较条件：=、[]、[}、{]、{}<br>
   *                '='：相等，返回准确的下标<br>
   *                '[]'：大于等于前一个，并且小于等于后一个，返回前一个下标<br>
   *                '[}'：大于等于前一个，并且小于后一个，返回前一个下标<br>
   *                '{]'：大于前一个，并且小于等于后一个，返回前一个下标<br>
   *                '{}'：大于前一个，并且小于后一个，返回前一个下标
   * @tparam T 数组元素的类型，必须实现Comparable接口。<b>注意，如果是使用数字类型，则必须使用java中的包装类，scala的数字类型并没有实现比较接口</b>
   * @return 数组下标，如果没有符合条件的值，则返回-1。<br>
   *         <b>注意，一定要对返回值-1进行特殊处理，直接作为数组下标使用，会造成下标越界异常</b>
   */
  def binarySearch[T <: Comparable[T]](a: Array[T], value: T, compare: String): Int = {
    val index = binarySearch(a, value)
    val length = a.length
    compare match {
      case "=" => {
        if (value.compareTo(a(index)) == 0) index else -1
      }
      case "[]" => {
        if (index == length - 1) {
          // 返回下标为最后一个元素下标，则只需要比较该位置元素是否小于等于指定值即可
          if (value.compareTo(a(index)) <= 0) index else -1
        } else {
          if (value.compareTo(a(index)) >= 0 && value.compareTo(a(index + 1)) <= 0) index else -1
        }
      }
      case "[}" => {
        if (index == length - 1) {
          // 返回下标为最后一个元素下标，则只需要比较该位置元素是否小于指定值即可
          if (value.compareTo(a(index)) < 0) index else -1
        } else {
          if (value.compareTo(a(index)) >= 0 && value.compareTo(a(index + 1)) < 0) index else -1
        }
      }
      case "{]" => {
        if (index == length - 1) {
          // 返回下标为最后一个元素下标，则只需要比较该位置元素是否小于等于指定值即可
          if (value.compareTo(a(index)) < 0) index else -1
        } else {
          if (value.compareTo(a(index)) > 0 && value.compareTo(a(index + 1)) <= 0) index else -1
        }
      }
      case "{}" => {
        if (index == length - 1) {
          // 返回下标为最后一个元素下标，则只需要比较该位置元素是否小于指定值即可
          if (value.compareTo(a(index)) < 0) index else -1
        } else {
          if (value.compareTo(a(index)) > 0 && value.compareTo(a(index + 1)) < 0) index else -1
        }
      }
      case _ => -1
    }
  }

  /**
   * 二分查找<br>
   * 根据数组和给定值，找到指定值在数字中可能的所在位置<br>
   * 如果找到了相等的值，则返回数值所在下标。如果没找到相等的值，但是找到了合适的位置（在两个值之间），则返回前面那个值的下标
   *
   * @param a     数组，要求元素已经自然排序
   * @param value 待查找值
   * @tparam T 数组元素的类型，必须实现Comparable接口
   * @return 数组下标。如果待查找值比数组第一个值小，则返回下标0；如果待查找值比数组最后一个值还要大，则返回最后一个数字的下标。
   */
  private def binarySearch[T <: Comparable[T]](a: Array[T], value: T): Int = {
    var high: Int = a.length - 1
    var low: Int = 0
    var middle: Int = -1
    var count: Int = 0
    breakable {
      while (true) {
        count += 1
        middle = (low + high) >>> 1
        if (middle <= 0 || middle >= a.length - 1) break()
        if (value.compareTo(a(middle)) >= 0 && value.compareTo(a(middle + 1)) <= 0) {
          break()
        } else {
          if (value.compareTo(a(middle)) < 0) {
            high = middle - 1
          }
          if (value.compareTo(a(middle + 1)) > 0) {
            low = middle + 1
          }
        }
      }
    }
    println(s"value: $value, count: ${count}")
    middle
  }

}
